/**
 * sOSPF.java
 *
 * @author Philip Kwok
 * @author Myongsu Choe
 */


package SSF.OS.OSPF;


import java.io.*;
import java.util.*;
import com.renesys.raceway.SSF.*;
import com.renesys.raceway.DML.*;
import SSF.Net.*;
import SSF.Net.Util.*;
import SSF.OS.*;
import SSF.OS.BGP4.Util.AS_descriptor;
import SSF.OS.BGP4.Util.IPaddress;


// ===== class SSF.OS.OSPF.sOSPF =========================================== //
/**
 * The OSPF interior gateway protocol (IGP).
 *
 * @author Philip Kwok
 */
public class sOSPF extends ProtocolSession implements FIBChangeListener {

  // ......................... constants ........................... //

  // - - - - - - - - OSPF router types - - - - - - - - //
  /** Indicates an internal OSPF router. */
  public static final int INTERNAL    = 1;
  /** Indicates an OSPF area border router. */
  public static final int AREA_BORDER = 2;
  /** Indicates an OSPF backbone router. */
  public static final int BACKBONE    = 3;
  /** Indicates an OSPF AS boundary router. */
  public static final int AS_BOUNDARY = 4;

  // - - - - - - - - timing intervals - - - - - - - - //
  /** The interval at which OSPF determines the router types. */
  public static final double GET_RT_TYPE_ITVL    = 10.0;
  /** The interval at which OSPF sends hello packets. */
  public static final double HELLO_INTERVAL      = 10.0;
  /** The interval at which OSPF sends LSAs. */
  public static final double SEND_LSA_ITVL       = 10.0;
  /** The interval at which OSPF rebuilds its routing tables. */
  public static final double BUILD_RT_TABLE_ITVL = 10.0;

  // - - - - - - - - neighbor states - - - - - - - - //
  /** Indicates that a given neighbor is down. */
  public static final int DOWN        = 1;
  /** Indicates that a hello has been received from a given neighbor. */
  public static final int HELLO_RCVD  = 2;
  /** Indicates that an adjacency exists with a given neighbor. */
  public static final int ADJACENT    = 3;

  // - - - - - - - - link types - - - - - - - - //
  /** Indicates a point-to-point connection to another router. */
  public static final int POINT_TO_POINT = 21;
  /** Indicates a connection to a transit network. */
  public static final int TO_TRANSIT     = 22;
  /** Indicates a connection to a stub network. */
  public static final int TO_STUB        = 23;
  /** Indicates a connection to an AS boundary router. */
  public static final int TO_AS_BOUNDARY = 24;
  /** Indicates a connection to a host. */
  public static final int TO_HOST        = 25;

  // - - - - - - - - multicast addresses - - - - - - - - //
  /** The int value of the multicast address for ALLSPFRouters (All Shortest
   *  Path First Routers). The real IP address is 224.0.0.5, but here we will
   *  use Integer.MAX_VALUE - 10. */
  public static final int ASPF_MCAST_ADDR  = Integer.MAX_VALUE - 10;
  public static final int DESIG_MCAST_ADDR = Integer.MAX_VALUE - 11;

  // ........................ member data .......................... //

  /** A reference to the top-level Net. */
  public static Net topnet;

  /** The local router. */
  private Router rtr;

  /** The host ID of the local router. */
  public int hostid;

  /** The NHI address prefix of the local router. */
  public String nh;

  /** The identity of this router.  It is chosen as the smallest of the IP of
   *  all its interfaces (in A.B.C.D/bits form). */
  private int rtrid;
  private int c=0;

  /** Indicates if this is an internal Router. */
  public boolean internal_rtr;

  /** Indicates if this is an area border router. */
  public boolean area_border_rtr;

  /** Indicates if this is a backbone router. */
  public boolean backbone_rtr;

  /** Indicates if this is an AS boundary router. */
  public boolean as_boundary_rtr;

  /** The NHI address prefix of the AS to which this router belongs. */
  public String as_nh;

  /** The number of the AS to which this router belongs. */
  public int as_num = AS_descriptor.NO_AS;

  /** The Area to which this router belongs. */
  public int area_num = -1;

  /** The Area(s) to which this route belongs. A router can belong to at most 2
   * areas, ie, the backbone and a non-backbone area.  */
  public int[] areas;

  /** The OSPF interface data structure. */
  public Interface[] ifs;

  /** The link state database implemented as an adjacency list. */
  public LSDatabase lsdb;

  /** The local router's forwarding table. */
  public RoutingTable fwd_table;

  /** Packet sequence number, which is supposed to be unique for all OSPF LSA
    * packets. Currently, it starts at "nh+1" for all routers.  */
  private int seqnum;

  /** An array storing all the seqnums of all packets received */
  private String[] seqnum_rcvd;

  /** The index of the next slot to insert in seqnum_rcvd. */
  private int seqnum_index;

  /** A reference to the underlying IP protocol session. */
  IP ip;

  /** Whether or not a validation test message has yet been printed (since it
   *  only needs to be done once (by one OSPF instance)). */
  private static boolean vmsg_printed = false;

  /** A helper to manage debugging. */
  public Debug debug;

  /** Whether or not global OSPF options have yet been configured (since it
   *  only needs to be done once, by one OSPF instance). */
  private static boolean options_configured = false;


  // ----- sOSPF.config ---------------------------------------------------- //
  public void config(Configuration cfg) throws configException {
    super.config(cfg);

    String str;
    // set a few member fields that may get referenced before init is called
    rtr    = (Router)inGraph(); // the local router
    topnet = rtr.net;  // set a reference to the top-level Net
    hostid = rtr.ID;
    nh     = rtr.nhi;

    try {
      // get the top-level Net's CIDR block
      cidrBlock blk = rtr.defined_in_network();
      while (blk.nhi_parent() != null) {
        blk = blk.nhi_parent();
      }
      Configuration allospfcfg =
           (Configuration)blk.networkConfiguration().findSingle("ospfoptions");
      config_options(allospfcfg);
    } catch (configException cex) {
      debug.err("problem configuring OSPF options");
      cex.printStackTrace();
    }

  }

  // ----- constructor sOSPF ----------------------------------------------- //
  /**
   * Constructs an OSPF protocol session.
   */
  public sOSPF() {
    debug = new Debug(this);
  }

  // ----- sOSPF.routeAddedBy ---------------------------------------------- //
  /**
   * Notification that the named protocol has added a new entry to the
   * forwarding table on this host.
   *
   * @param rinfo         Information about the route added to the FIB.
   * @param protocolName  The name of the protocol that added the route.
   */
  public void routeAddedBy(RoutingInfo rinfo, String protocolName) {
    if (protocolName.equals("BGP") || protocolName.equals("EBGP")) {
      IPaddress ipa = new IPaddress(rinfo.dest_ip());
      acceptASExternalRoute(ipa.masked_intval(),ipa.prefix_len());
    }
  }

  // ----- sOSPF.routeDeletedBy -------------------------------------------- //
  /**
   * Notification that the named protocol has removed an entry from the
   * forwarding table on this host.
   *
   * @param rinfo         Information about the route deleted from the FIB.
   * @param protocolName  The name of the protocol that deleted the route.
   */
  public void routeDeletedBy(RoutingInfo rinfo, String protocolName) {
    if (protocolName.equals("BGP") || protocolName.equals("EBGP")) {
      // needs to be implemented!
    }
  }

  // ----- sOSPF.config_options -------------------------------------------- //
  /**
   * Configures options set with the <code>ospfoptions</code> attribute in DML.
   * Only one OSPF instance in the entire simulation will actually execute this
   * method in its entirety.  This is because the options configured here are
   * those which apply globally to all OSPF instances.  The one OSPF instance
   * that executes this method does so on behalf of all OSPF instances in the
   * simulation.
   *
   * @param cfg  Contains the values of configurable OSPF options.
   */
  private static synchronized void config_options(Configuration cfg) {
    if (options_configured) {
      return;
    }
    // only one sOSPF instance will actually get this far
    options_configured = true;
    try {
      Options.config(cfg);
    } catch (configException c) {
      Debug.gerr(c.toString());
      c.printStackTrace();
    }
  }

  // ----- sOSPF.print_validation_test_msg --------------------------------- //
  /**
   * Prints a validation test message if the current model being executed is
   * part of a validation test.  It is here separately so that it can be
   * synchronized, so that it gets executed exactly once during the run.
   *
   * @param ospf  The OSPF protocol session that is calling this class method.
   */
  private static synchronized void print_validation_test_msg(sOSPF ospf) {
    if (vmsg_printed) {
      return;
    }
    // only one instance of sOSPF will actually get this far
    vmsg_printed = true;
    ospf.debug.valid(Options.validation_test, 0);
  }

  // ----- sOSPF.init ------------------------------------------------------ //
  /**
   * Initialization routine called by ProtocolGraph after instantiation.
   * Information that OSPF needs in the setup stage include:
   * 1. a reference to the IP protocol
   * 2. a reference to the router in which this OSPF sits
   * 3. the level numbers of the router, which says which AS and area this
   *    router is in
   */
  public void init() {

    // - - - - - - - - print validation test message - - - - - - - -
    // if this is a validation test, print initial test message
    if (Options.validation_test != -1) {
      print_validation_test_msg(this);
    }

    try {
      ip = (IP)rtr.SessionForName("ip");
      ip.open(this, null);
    } catch (ProtocolException pex) {
      debug.err("couldn't get a reference to (or couldn't open()) IP");
      pex.printStackTrace();
    }
    fwd_table = ip.getRoutingTable();

    // Make sure that OSPF hears about changes to the forwarding table.
    fwd_table.addFIBChangeListener(this);

    rtrid = Integer.MAX_VALUE;

    // Get AS and area ids to which this router is attached.
    as_nh  = AS_descriptor.get_as_nh(rtr);
    as_num = AS_descriptor.nh2as(as_nh);
    area_num = area_descriptor.get_area_num(rtr);
    if (area_num == area_descriptor.NO_AREA) {
      System.err.println("OSPF router was not contained by an OSPF area");
      System.exit(-1);
    }

    lsdb = new LSDatabase(this);
    seqnum_index = 0;
    seqnum_rcvd  = new String[100];
    seqnum       = 1;

    // print initial routing table
    debug.msg(Options.FWD_TABLE, 1);

    // print each router's AS and area number
    debug.msg(Options.AS_NUM);
    debug.msg(Options.AS_AREA);

    // The methods makeHelloProcess() and makeSendLSAProcess() will
    // be called after this timer expires.
    (new StartupTimer(this,1)).set();
  }

  // ----- sOSPF.nowsec ---------------------------------------------------- //
  /**
   * Returns the current simulation time in seconds.
   *
   * @return the current simulation time in seconds
   */
  public double nowsec() {
    return ((double)(inGraph().now()))/((double)Net.frequency);
  }

  // ----- sOSPF.getNextSeqNum --------------------------------------------- //
  /**
   * Returns the next LSA sequence number of this OSPF session.
   * changed a sequence number to have unique one. // revised by msc.
   * the sequence number has the following structure: router_nh+seqnum,
   * where the number itself is a string not an integer.
   */
  private int getNextSeqNum() {
    addRcvdSeqNum(seqnum,nh);
    return seqnum++;
  }

  // ----- sOSPF.addRcvdSeqNum --------------------------------------------- //
  /**
   * Adds a sequence number to the list of received sequence numbers.
   */
  private void addRcvdSeqNum(int seq_num, String nhipref) {
    String seqno = nhipref+"+"+seq_num;
    if (seqnum_index + 1 == seqnum_rcvd.length) {
      seqnum_index = 0;
    }
    seqnum_rcvd[seqnum_index++] = seqno;
  }

  // ----- sOSPF.seqNumInList ---------------------------------------------- //
  /**
   * Returns true if the given sequence number is in the seq number list.
   */
  private boolean seqNumInList(int seq_num, String nhipref) {
    String seqno = nhipref+"+"+seq_num;
    for (int i=0; i<=seqnum_rcvd.length; i++) {
      if (seqnum_rcvd[i] == null) return false;
      if (seqnum_rcvd[i].equals(seqno)) return true;
    }
    return false;
  }

  // ----- sOSPF.initInterfaces -------------------------------------------- //
  private void initInterfaces() {
    ifs = new Interface[ip.INTERFACE_COUNT];
    int type, peer_areaid, cost, ptpAddr;
    String peer_asnh;
    String peer_nh = "null";
    NIC next_itrf;
    boolean isPTP = false; // boolean indicating if this interface is PTP

    for (int i=0; i<ip.INTERFACE_COUNT; i++) {
      // reinitialize interface values
      type         = -1;
      peer_asnh    = "";
      peer_areaid  = 0;
      peer_nh      = "null";
      cost         = 1;  // can have method to insert weight from NIC or Link
      ptpAddr      = -1;
      isPTP        = false;

      next_itrf = (NIC)ip.INTERFACE_SET[i];
      isPTP = (next_itrf.link_hw instanceof ptpLinkLayer);

      // if point-to-point link
      if (isPTP) {
        type     = POINT_TO_POINT;
        NIC peer = (NIC)next_itrf.link_hw.peers(next_itrf).nextElement();
        ptpAddr  = peer.ipAddr;
        Host peerHost = (Host)((NIC)peer).inGraph();

        // check if peer host is running OSPF
        if (peerHost instanceof Router) {
          sOSPF peerOSPF = null;
          try {
            peerOSPF = (sOSPF)((NIC)peer).inGraph().SessionForName("ospf");
            peer_asnh = peerOSPF.as_nh;
            peer_areaid = peerOSPF.area_num;
          }
          catch (ProtocolException pex) {
            // peer is not running OSPF
          }
        } else { // peer host is not a router
          type = TO_HOST;
          peer_asnh = as_nh;
          peer_areaid = area_num;
        }
        // if (peerOSPF == null) type = TO_STUB;

        peer_nh = peerHost.nhi;
      } else { // if this is a network link
        type = TO_STUB; // this is now analogous to "TO_LAN"
        peer_asnh   = as_nh;
        peer_areaid = area_num;
        peer_nh = nh;
      }

      ifs[i] = new Interface(type, next_itrf.ipAddr, ptpAddr,
                             (byte)next_itrf.maskBits, DOWN, nh, as_nh,
                             area_num, peer_asnh, peer_areaid, peer_nh, cost);
        
      // sets the rtrid
      if (next_itrf.ipAddr < rtrid) {
        rtrid = next_itrf.ipAddr;
      }
    }
    debug.msg(Options.IFS);
    debug.valid(Options.INTERFACES1, 1);
    debug.valid(Options.INTERFACES2, 1);
  }

  // ----- sOSPF.determineRouterType --------------------------------------- //
  /**
   * Determine router type by comparing area number and AS id to those if its
   * peers.
   */
  private void determineRouterType() {
    if (ifs == null) { return; }

    internal_rtr    = false;
    backbone_rtr    = false;
    area_border_rtr = false;
    as_boundary_rtr = false;

    boolean sameArea = true;
    boolean sameAs = true;
    boolean backBoneArea = false;

    for (int i=0; i<ifs.length; i++) {
      if (area_num == 0) { backBoneArea = true; }
      if (!ifs[i].peer_as_nh.equals(as_nh)) { sameAs = false; }
      if (ifs[i].peer_area_num != area_num) { sameArea = false; }
    }
    if (sameAs && !sameArea) { area_border_rtr = true; }
    if ((!sameAs && sameArea) || (!sameAs && !sameArea)) {
      as_boundary_rtr = true;
    }
    if (backBoneArea) { backbone_rtr = true; }
    if (sameAs && sameArea) { internal_rtr = true; }
    debug.msg(Options.RTR_TYPE);
    debug.valid(Options.ROUTERTYPE1, 1);
    debug.valid(Options.ROUTERTYPE2, 1);

    if (area_border_rtr) {
      // Until multiple areas are used, no area border routers should exist
      System.err.println("Error: OSPF Area Border Router not expected");
      System.exit(-1);
    }
  }

  // ----- sOSPF.createLinkDatabase ---------------------------------------- //
  /**
   * Queries the list of all routers and links from Net, decides connection
   * types, and creates a link state database.
   */
  public void createLinkDatabase() {
    Enumeration enum, enum2;
    for (enum=rtr.getNet().hosts.elements(); enum.hasMoreElements();) {

      Host H = (Host)enum.nextElement();
      if (H instanceof Router) {
        int i=0;
        sOSPF peerOSPF = null;
        try {
          peerOSPF = (sOSPF)H.SessionForName("ospf");
        } catch (ProtocolException pex) {
          // router was not running OSPF, that's OK
        }

        // only consider routers running OSPF in the same AS as me
        if (peerOSPF != null && peerOSPF.as_nh.equals(as_nh)) {

          for (enum2=H.interfaceNumbers.elements();
                                                enum2.hasMoreElements(); i++) {
            boolean add = true;
            NIC nic = (NIC)enum2.nextElement();

            // if this is a ptp link
            if (nic.link_hw instanceof ptpLinkLayer) {
              NIC peer = (NIC)nic.link_hw.peers(nic).nextElement();
              try {
                Host peerHost = (Host)peer.inGraph();
                if (peerHost instanceof Router) {
                  // refer to RFC2328:12.4.1.1 (Option 2)
                  sOSPF peerHostOSPF = (sOSPF)peerHost.SessionForName("ospf");

                  if (peerHostOSPF.as_nh.equals(as_nh)) {
                    // it doesn't cross an AS boundary
                    lsdb.updateLink(LSDatabase.ROUTER_LINK, H.nhi,
                                    new LinkInfo(0, peerHost.nhi,
                                                 POINT_TO_POINT,
                                                 peer.ipAddr, i, 0, 1));
                    // (this is Option 2 of RFC2328:12.4.1.1)
                    lsdb.updateLink(LSDatabase.ROUTER_LINK, H.nhi,
                                 //new LinkInfo(0,peerHost.nhi+"("+nic.ID+")",
                                   new LinkInfo(0, H.nhi,
                                   TO_STUB, IP_s.mask(nic.ipAddr,nic.maskBits),
                                   nic.maskBits, 0, 1));
                  }
                } else {
                  // to a host
                  lsdb.updateLink(LSDatabase.ROUTER_LINK, H.nhi,
                                //new LinkInfo(0, peerHost.nhi, TO_HOST,
                                  new LinkInfo(0, H.nhi, TO_HOST,
                                               peer.ipAddr, 32, 0, 1));
                }
              }
              catch (ProtocolException e) {
                // OSPF is not running at the neighboring router.  Assume (for
                // now) that it's in a different AS.
              }
             } else if (nic.isVirtual) { // virtual interface
               // treat as stub link to the interface (see RFC2328:12.4.1)
               lsdb.updateLink(LSDatabase.ROUTER_LINK, H.nhi,
                             //new LinkInfo(0, H.nhi+"("+nic.ID+")", TO_STUB,
                               new LinkInfo(0, H.nhi, TO_STUB,
                                            nic.ipAddr, 32, 0, 1));
            } else { // this is a link to a stub network
              lsdb.updateLink(LSDatabase.ROUTER_LINK, H.nhi,
                            //new LinkInfo(0, H.nhi+"("+nic.ID+")", TO_STUB,
                              new LinkInfo(0, H.nhi, TO_STUB,
                                           IP_s.mask(nic.ipAddr, nic.maskBits),
                                           nic.maskBits, 0, 1));
            }
          }
        }
      }
    }
    debug.msg(Options.LSDB, 1);
    debug.valid(Options.LSDB1, 1);
    debug.valid(Options.LSDB2, 1);

    buildRoutingTable();

  } // end createLinkDatabase()

  // ----- sOSPF.push ------------------------------------------------------ //
  public boolean push(ProtocolMessage message, ProtocolSession fromSession)
                                                     throws ProtocolException {
    try {
      if (message instanceof Packet) {
        Packet pkt = (Packet)message;
        switch (pkt.typ) {
        case Packet.DATABASE:
          processLSApkt(pkt);
          return true;
        default:
          return true;
        }
      }
    }
    catch (Exception e) {
      System.err.println(e);
    }
    return true;
  }

  // ----- sOSPF.sendOSPFheaderItrf ---------------------------------------- //
  /**
   * Sends an OSPF packet out on an interface.
   */
  private boolean sendOSPFheaderItrf(Packet pkt, Interface Itrf) {
    if (Itrf.typ == POINT_TO_POINT) {
      IpHeader ipHeader = new IpHeader(Protocols.OSPF_PRTL_NUM,
                                       Itrf.ipaddr, Itrf.p2paddr);
      ipHeader.carryPayload(pkt);
      try {
        return ip.push(ipHeader, sOSPF.this);
      } catch (ProtocolException e) {
        e.printStackTrace();
        System.err.println("OSPF: OSPF Packet not sent");
        return false;
      }
    }// else if (Itrf.typ == TO_STUB) {
    //  for (int i = 0; i < ip.INTERFACE_COUNT; i++) {
    //    if (ip.INTERFACE_SET[i].ipAddr == Itrf.ipaddr) {
    //      NIC next_itrf = (NIC) ip.INTERFACE_SET[i];
    //      for (Enumeration lanitf = next_itrf.link_hw.peers(next_itrf);
    //           lanitf.hasMoreElements();) {
    //        NIC lan = (NIC)lanitf.nextElement();
    //        IpHeader ipHeader = new IpHeader
    //          (Protocols.OSPF_PRTL_NUM, Itrf.ipaddr, lan.ipAddr);
    //        ipHeader.carryPayload (pkt);
    //        try { return ip.push (ipHeader, sOSPF.this); }
    //        catch (ProtocolException e) {
    //          e.printStackTrace();
    //          System.err.println ("OSPF: OSPF Packet not sent");
    //          return false;
    //        }
    //      }
    //      break;
    //    }
    //  }
    //}
    return true;
  }

  // ----- sOSPF.sendLSAListAllItrf ---------------------------------------- //
  /**
   * Sends a list of link information to all interfaces. This method allows you
   * decide if you want to send the list to interfaces belonging to the
   * specified area argument (thisArea) using the boolean argument (sameArea).
   */
  private void sendLSAListAllItrf(int LSAtype, int lsid, Vector linkinfolist,
                                  boolean sameArea, int thisArea) {
    boolean proceed;
    int next_seq_num = getNextSeqNum();
    for (int i=0; i<ifs.length; i++) {
      proceed = false;

      // Decide if we want to send the list to interfaces that belong to the
      // same area as "thisArea".
      if (sameArea) {
        if (ifs[i].area_num == thisArea && ifs[i].peer_as_nh.equals(as_nh)) {
          proceed = true;
        } else {
          proceed = false;
        }
      } else {
        if (ifs[i].area_num != thisArea) {
          proceed = true;
        } else {
          proceed = false;
        }
      }
      if (proceed) {
        LSA lsa = new LSA(next_seq_num,  // sequence number
                          LSAtype,       // LSA type
                          lsid,          // Link State ID: OSPF router ID
                          hostid,        // Advertising Router
                          nh,            // Advertising Router's NHI address
                          linkinfolist); // the list of link info to send

        Packet pkt = new Packet(Packet.DATABASE,   // OSPF Packet type
                                ifs[i].ipaddr,     // Originator's IP address
                                nh,                // Router NHI prefix
                                ifs[i].as_nh,      // AS num
                                ifs[i].area_num);  // Area num

        pkt.carryPayload(lsa);
        sendOSPFheaderItrf(pkt, ifs[i]);
        debug.msg(Options.LSA, 1);
      }
    }
  }

  // ----- sOSPF.processLSApkt --------------------------------------------- //
  /**
   * This method processes a Link State Advertisement.  It doesn't do anything
   * in this implementation. It is called by the push() method.
   */
  private void processLSApkt (Packet pkt) {
    LSA lsaheader = (LSA) pkt.payload ();
    switch (lsaheader.typ) {
    case LSA.AS_EXTERNAL_LSA:
      processType5LSA (pkt);
      break;
    default :
      break;
    }
  }

  // ----- sOSPF.getSimTime ------------------------------------------------ //
  /**
   * Get the current simulation.
   */
  public float getSimTime() {
    return this.inGraph().now()/((float)SSF.Net.Net.seconds(1.0));
  }

  // ----- sOSPF.acceptASExternalRoute(int,int) ---------------------------- //
  /**
   * This method is called by other inter-AS routing protocols, e.g. BGP, to
   * tell OSPF about AS External Routes.
   */
  private void acceptASExternalRoute(int destNetworkIP, int destNetworkMask) {
    acceptASExternalRoute(nh, destNetworkIP, destNetworkMask);
  }

  // ----- sOSPF.acceptASExternalRoute(String,int,int) --------------------- //
  /**
   * This method is called invoked to tell OSPF about AS External Routes.
   */
  private void acceptASExternalRoute(String forwardRtrNH, int destNetworkIP,
                                     int destNetworkMask) {

    debug.msg(Options.LSDB, 2, destNetworkIP, destNetworkMask);
    LinkInfo linkinfo = new LinkInfo(forwardRtrNH, rtrid, destNetworkMask,
                                     LSA.AS_EXTERNAL_LSA);
    Vector asExtLink = new Vector();
    asExtLink.addElement(linkinfo);

    // - - - - - - - - - - local processing - - - - - - - - - - //
    LinkInfo dbinfo = new LinkInfo(forwardRtrNH, destNetworkIP,
                                   destNetworkMask, LSA.AS_EXTERNAL_LSA);
    lsdb.updateLink(LSDatabase.AS_EXT, forwardRtrNH, dbinfo);

    buildRoutingTable();
    debug.msg(Options.LSDB, 1);

    // - - - - - - - - - - global processing - - - - - - - - - - //
    // floods the LSA to all other routers in the same AS
    if (as_boundary_rtr) {
      sendLSAListAllItrf(LSA.AS_EXTERNAL_LSA, destNetworkIP, asExtLink,
                         true, area_num);
      debug.msg(Options.LSA, 2);
    }
  }

  // ----- sOSPF.announceASExternalRoute ----------------------------------- //
  /**
   * This methods is the non-flooding way used by ASBRs to announce an AS
   * External Route to all routers in the same AS. It does this by calling
   * their acceptASExternalRoute() method directly.
   */
  private void announceASExternalRoute(int destNetworkIP,int destNetworkMask) {
    if (as_boundary_rtr) {
      Enumeration enum;
      for (enum=rtr.getNet().hosts.elements(); enum.hasMoreElements();) {
        Host H = (Host)enum.nextElement();
        if (H instanceof Router) {
          try {
            sOSPF hOSPF = (sOSPF)H.SessionForName("ospf");
            // if the router is not my router, and the router is in the same AS
            if (H.nhi.compareTo(nh) != 0 && hOSPF.as_nh.equals(as_nh)) {
              hOSPF.acceptASExternalRoute(nh, destNetworkIP, destNetworkMask);
            }
          }
          catch (ProtocolException pex) {
            pex.printStackTrace();
          }
        }
      }
    }
  }

  // ----- sOSPF.processType5LSA ------------------------------------------- //
  /**
   * Processes all incoming Type 5 (AS external routes) packets.
   */
  private void processType5LSA(Packet pkt) {

    debug.msg(Options.LSDB, 3);

    // check if the packet comes from a router in the same AS & area
    if (!(pkt.as_nh.equals(as_nh) && pkt.area_num == area_num)) {
      return;
    }

    LSA lsaheader = (LSA)pkt.payload();

    // check if received this LSA already
    if (seqNumInList(lsaheader.seqnum,lsaheader.adrtrnh)) {
      return;
    } else {
      addRcvdSeqNum(lsaheader.seqnum, lsaheader.adrtrnh);
    }

    int extNetworkIP = lsaheader.id;
    String advRtrNH = lsaheader.adrtrnh;

    // asExtLink is the list of link info
    Vector asExtLink = lsaheader.contents;

    // insert the AS Ext. link info into the database
    LinkInfo linkinfo = (LinkInfo)asExtLink.elementAt(0); // there's only one
    LinkInfo dbinfo = new LinkInfo(linkinfo.nh, extNetworkIP,
                                   linkinfo.link_data, linkinfo.TypeOneType);
    lsdb.updateLink(LSDatabase.AS_EXT, advRtrNH, dbinfo);

    buildRoutingTable();

    // forward the LSA to other neighbors
    for (int i=0; i<ifs.length; i++) {
      LSA lsa_header = new LSA(lsaheader.seqnum, lsaheader.typ, lsaheader.id,
                               lsaheader.adrtr, lsaheader.adrtrnh,
                               lsaheader.contents);

      Packet newpkt = new Packet(pkt.typ, pkt.rtrid, pkt.nh, pkt.as_nh,
                                 pkt.area_num);
        
      newpkt.carryPayload(lsa_header);
      sendOSPFheaderItrf(newpkt, ifs[i]);
      debug.msg(Options.LSDB, 4);      
    }
  }

  // ----- sOSPF.buildRoutingTable ----------------------------------------- //
  /**
   * Builds the shortest path tree using the databases.
   */
  private void buildRoutingTable() {
    if (!lsdb.isModified()) {
      System.out.println("OSPF::Router " + nh + "DB not modified, " +
                         "RT not updated");
      return;
    }

    initInterfaces();
    determineRouterType();
    if (lsdb != null) {
      if (lsdb.RouterLink.size() == 0) {
        return;
      }
        
      // - - - - - - - - - - - - - Phase I - - - - - - - - - - - - //
      // Calculate the shortest paths.  If all SPs can be calculated,
      // proceed to Phase II.
        
      Dijkstra dijkstra = new Dijkstra(lsdb.RouterLink, nh);

      boolean b1 = !dijkstra.findAllShortestPaths();
      boolean b2 = false;
      if (!b1) {
        b2 = !dijkstra.computed();
      }
      
      //if (!dijkstra.findAllShortestPaths() || !dijkstra.computed()) {
      if (b1 || b2) {
        return;
      }
        
      // - - - - - - - - - - - - - Phase II - - - - - - - - - - - - //
      // Retrieve all the networks in the OSPF Database.
        
      // get the network info for this area
      Vector allNets = lsdb.getStubNetworks();
        
      // get the network info for other areas
      Vector summarynet = getSummaryNets(lsdb.SummaryNet);
      for (int i=0; i<summarynet.size(); i++) {
        allNets.addElement(summarynet.elementAt(i));
      }

      // get the AS External Networks
      Vector asextnets = lsdb.getASExtNetworks();
      for (int i=0; i<asextnets.size(); i++) {
        allNets.addElement(asextnets.elementAt(i));
      }

      // - - - - - - - - - - - - - Phase III - - - - - - - - - - - - //
      // For each network in the database, find its nexthop and
      // corresponding interface & add those to the routing table.

      for (int i=0; i<allNets.size(); i++) {
        LinkInfo linkinfo = (LinkInfo)allNets.elementAt(i);
        int net_ip     = linkinfo.link_id;
        int net_mask   = linkinfo.link_data;
        int iface_ip   = -1;
        String nexthop_nh = dijkstra.nextHop(nh, linkinfo.nh);
        int nexthop_ip    = 0;
        
        // find the IP address of the interface corresponding to the next hop

        if (nexthop_nh.equals(nh)) {
          // next hop is either a host, stub network, or loopback interface

          for (int j=0; j<ifs.length; j++) {
            if (ifs[j].typ == TO_STUB &&
                (IP_s.mask(net_ip, net_mask) ==
                 IP_s.mask(ifs[j].ipaddr, ifs[j].ipmask))) {
              iface_ip = ifs[j].ipaddr;
              break;
            } else if (ifs[j].typ == TO_HOST &&
                       ifs[j].ipaddr == net_ip) {
              iface_ip = ifs[j].ipaddr;
              break;
            }
          }
        } else { // next hop is NOT a host, stub network, or loopback
          for (int j=0; j<ifs.length; j++) {
            if (ifs[j].peer_nh.equals(nexthop_nh)) {
              iface_ip = ifs[j].ipaddr;
              nexthop_ip = ifs[j].p2paddr;
              break;
            }
          }
        }

        if (iface_ip != -1) {
          // May need an area and path type as per RFC 2328?
          for (int k=0; k<ip.INTERFACE_COUNT; k++) {
            NIC useItrf = (NIC)ip.INTERFACE_SET[k];
            if (useItrf.ipAddr == iface_ip) {
              String dest = IP_s.IPtoString(net_ip) + "/" + net_mask;
              fwd_table.rep(IP_s.IPtoString(net_ip)+"/"+net_mask, useItrf,
                        nexthop_ip, dijkstra.getDistance(linkinfo.nh), "OSPF");
              debug.msg(Options.FWD_TABLE, 2, net_ip, net_mask, nexthop_nh);
              break;
            }
          }
        }
      }
      debug.msg(Options.FWD_TABLE, 1);
      debug.valid(Options.FWDTABLE1, 1);
      debug.valid(Options.FWDTABLE2, 1);
      lsdb.setModified(false);
    }
  }

  // ----- sOSPF.getSummaryNets -------------------------------------------- //
  /**
   * Returns a list of link information containing all the networks in the
   * given table that do not belong to the area(s) this OSPF router belongs to.
   */
  private Vector getSummaryNets(Hashtable mySumNet) {
    Vector SumNets = new Vector();

    String rtrnh = null;
    Vector linkinfolist = null;
    // for each link info list in the SummaryNet
    for (Enumeration enum=mySumNet.keys(); enum.hasMoreElements();) {
      rtrnh = (String)enum.nextElement();
      linkinfolist = (Vector)mySumNet.get(rtrnh);

      // for each link info item in the list
      for (int i=0; i<linkinfolist.size(); i++) {
        LinkInfo info = (LinkInfo)linkinfolist.elementAt(i);
        if (!oneOfAreas(info.area)) {
          LinkInfo newinfo = new LinkInfo(rtrnh, info.link_id, info.link_data);
          SumNets.addElement(newinfo);
        }
      }
    }
    return SumNets;
  }

  // ----- sOSPF.oneOfAreas ------------------------------------------------ //
  /**
   * Returns true if this router belongs to the given area.
   */
  private boolean oneOfAreas(int area) {
    for (int i=0; i<areas.length; i++) {
      if (area == areas[i]) {
        return true;
      }
    }
    return false;
  }

  // ===== inner class StartupTimer ======================================== //
  /**
   * A timer used to apply a brief waiting period before the link state
   * database is first calculated at startup.
   */
  private class StartupTimer extends SSF.OS.Timer {
    /** A reference to the calling OSPF protocol session. */
    sOSPF ospf;

    /** Construct a timer with the given duration. */
    public StartupTimer(sOSPF o, long duration) {
      super(o.inGraph(), duration);
      ospf = o;
    }

    /** A method to be performed when the timer expires.  It starts building
     *  the link state database. */
    public void callback() {
      ospf.createLinkDatabase();
    }
  } // end inner class StartupTimer


} // end class sOSPF
